﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.DynamicProgramming
{
    //01背包问题
    class Backpack
    {
        //================================================================、
        //有多件物品和一个最多能承受重量为bagSize 的背包。
        //第i件物品的重量是weight[i]，得到的价值是value[i] 。
        //每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
        public void BackPackProblem(int[] weight, int[] value, int bagSize)
        {//二维数组
            //dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
            int[,] dp = new int[weight.Length + 1, bagSize + 1];

            //==================数组初始化
            for(int i = 0;i< bagSize; i++)
            {//如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
                dp[i, 0] = 0;
            }
            for (int j = 0;j<weight[0];j++)
            {//很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
                dp[0, j] = 0;
            }
            for(int j = weight[0]; j >= bagSize;j++)
            {//当j >= weight[0]是，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。
                dp[0, j] = value[0];
            }

            //======================遍历
            for(int i = 1;i<weight.Length;i++)
            {//遍历物品
                for(int j = 0;j<= bagSize; j++)
                {
                    //递推公式
                    if (j < weight[i])
                        //物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。
                        dp[i, j] = dp[i - 1, j];
                    else
                        //当物品能放进背包
                        //dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值
                        //dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
                        dp[i, j] = Math.Max(dp[i - 1, j], dp[i - 1, j - weight[i]] + value[i]);
                }
            }
        }

        public void BackPackProblem_2(int[] weight, int[] value, int bagSize)
        {//滚动数组（一维数组）
         //滚动数组需要的条件是上一层可以重复利用，直接拷贝到当前层

            //dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
            int[] dp = new int[bagSize + 1];

            //===========================初始化
            dp[0] = 0;//背包容量为0所背的物品的最大价值就是0。

            for(int i = 0;i<weight.Length;i++)
            {// 遍历物品
                for (int j = bagSize;j >= weight[i];j--)
                {// 遍历背包容量,倒叙遍历是为了保证物品i只被放入一次
                    dp[j] = Math.Max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }

        //=====================================================力扣416 分割等和子集
        //给你一个只包含正整数的非空数组nums。
        //请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等
        public bool CanPartition(int[] nums)
        {//转换为背包问题
            //背包的体积为sum / 2
            //背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
            //背包如果正好装满，说明找到了总和为 sum / 2 的子集。
            //背包中每一个元素是不可重复放入。

            int sum = 0;
            for (int i = 0; i < nums.Length; i++)
                sum += nums[i];
            if (sum % 2 == 1)
                return false;
            int target = sum / 2;

            //定义dp数组
            // dp[i]中的i表示背包内总和
            // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
            // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
            //背包总容量是i，最大可以凑成i的子集总和为dp[i]。
            int[] dp = new int[1001];

            //初始化，只包含正整数，则可以初始化为0，如果包含负数，则需将非0下标初始化为负无穷
            dp[0] = 0;

            for(int i = 0;i<nums.Length;i++)
            {
                for(int j = target;j>=nums[i];j--)
                {// 每一个元素一定是不可重复放入，所以从大到小遍历
                    dp[j] = Math.Max(dp[j], dp[j - nums[i]] + nums[i]);
                }
            }

            // 集合中的元素正好可以凑成总和target
            if (dp[target] == target)
                return true;
            return false;
        }

        //============================================力扣1049 最后一块石头的重量2
        //有一堆石头，每块石头的重量都是正整数。
        //每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
        //如果 x == y，那么两块石头都会被完全粉碎；
        //如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
        //最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
        // <= stones.length <= 30
        //1 <= stones[i] <= 100
        public int LastStoneWeight2(int[] stones)
        {//思路：尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

            int sum = 0;
            foreach (int i in stones)
                sum += i;
            int target = sum / 2;

            int[] dp = new int[1501];

            for(int i = 0;i<stones.Length;i++)
            {
                for(int j = target;j>= stones[i];j--)
                {
                    dp[j] = Math.Max(dp[j], dp[j - stones[i]] + stones[i]);
                }
            }

            return sum - dp[target] * 2;
        }

        //==============================================力扣494 目标和
        //给你一个整数数组 nums 和一个整数 target 。
        //向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
        //例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
        //返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
        //1 <= nums.length <= 20
        //0 <= nums[i] <= 1000
        //0 <= sum(nums[i]) <= 1000
        //-1000 <= target <= 1000
        public int FindTargetSumWays(int[] nums, int target)
        {//思路：假设有加有减，设加法之和为left，减法之和为right
            //即有left - right = target;left + right = sum;
            //所以 left - (sum - left) = target -> left = (target + sum) / 2
            //同时 sum - right - right = target; right = (sum - target) / 2;
            //问题即是找出和为left或right的组合

            int sum = 0;
            foreach (int i in nums)
                sum += i;
            if (target > sum)
                return 0;
            int diff = sum - target;
            if (diff < 0 || diff % 2 != 0)
                return 0;
            
            int bagSize = (diff) / 2;
            //填满j（包括j）这么大容积的包，有dp[i]种方法
            int[] dp = new int[bagSize + 1];
            dp[0] = 1;
            for(int i = 0;i<nums.Length;i++)
            {
                for(int j = bagSize;j>= nums[i];j--)
                {
                    //求装满背包有几种方法的情况下，递推公式一般为：
                    dp[j] += dp[j - nums[i]];
                }
            }
            return dp[bagSize];
        }

        //====================================================力扣474 一和零
        //给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
        //请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
        //如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
        public int FindMaxForm(string[] strs, int m, int n)
        {//本题中strs 数组里的元素就是物品，每个物品都是一个！
         //而m 和 n相当于是一个背包，两个维度的背包。

            //最多有m个0和n个1的stars的最大子集大小为dp[m,n]
            int[,] dp = new int[m + 1, n + 1];

            //因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

            int oneNum = 0, zeroNum = 0;
            foreach(string str in strs)// 遍历物品
            {
                oneNum = 0;
                zeroNum = 0;
                foreach(char c in str)
                {
                    if (c == '0')
                        zeroNum++;
                    else
                        oneNum++;
                }

                for (int i = m;i>=zeroNum;i--)// 遍历背包容量且从后向前遍历！
                {//注意此处两个维度背包所以遍历两次
                    for(int j = n;j>=oneNum;j--)
                    {//zeroNum,oneNum是当前str的0和1的个数，所以i - zeroNum，j - oneNum就是前一个str的0和1的个数
                        dp[i, j] = Math.Max(dp[i, j], dp[i - zeroNum, j - oneNum] + 1);
                    }
                }
            }
            return dp[m, n];
        }
    }
}
